package leetcode_day._2021._202109._2130;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/9/24 16:00
 * 扁平化多级双向链表
 * 算法：链表  深度优先搜索
 */
public class _24_430 {
    class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
    }

    public Node flatten(Node head) {
        Node ans = new Node();
        ans.next = head;
        while (head != null) {
            if (head.child == null) head = head.next;
            else {
                Node tmp = head.next;
                Node childHead = flatten(head.child);
                head.next = childHead;
                childHead.prev = head;
                head.child = null;
                // 这里可以优化，将时间复杂度从 O(n * n) 优化成 O(n)
                while (head.next != null) head = head.next;
                if (tmp != null) tmp.prev = head;
                head = tmp;
            }
        }
        return ans.next;
    }

    public Node flatten_fasten(Node head) {
        dfs(head);
        return head;
    }
    Node dfs(Node head) {
        Node last = head;
        while (head != null) {
            if (head.child == null) {
                last = head;
                head = head.next;
            } else {
                Node tmp = head.next;
                Node childLast = dfs(head.child);
                head.next = head.child;
                head.child.prev = head;
                head.child = null;
                childLast.next = tmp;
                if (tmp != null) tmp.prev = childLast;
                last = head;
                // 这里不能写 head = tmp，不然就跳了 childLast
                // 如果写 head = tmp，那么上面就要写 last = childLast
                head = childLast;
            }
        }
        return last;
    }
}
